package LeetCode;

import java.util.HashSet;
import java.util.Set;

public class LC_683_KEmptySlots {

    public static void main(String[] args) {

    }

    class BITree {
        int[] tree;
        int len;

        BITree(int len) {
            tree = new int[len + 1];
            this.len = len;
        }

        void update(int idx, int val) {
            idx++;
            while (idx <= len) {
                tree[idx] += val;
                idx += idx & (-idx);
            }
        }

        int get(int idx) {
            int sum = 0;
            idx++;
            while (idx > 0) {
                sum += tree[idx];
                idx -= idx & (-idx);
            }
            return sum;
        }
    }

    public class Solution {
        public int kEmptySlots(int[] flowers, int k) {
            int n = flowers.length;
            BITree bit = new BITree(n);
            Set<Integer> set = new HashSet<>();
            for (int i = 0; i < n; i++) {
                int idx = flowers[i] - 1;
                set.add(idx);
                bit.update(idx, 1);
                if (set.contains(idx - k - 1) && bit.get(idx) - bit.get(idx - k - 2) == 2) {
                    return i + 1;
                } else if (set.contains(idx + k + 1) && bit.get(idx + k + 1) - bit.get(idx - 1) == 2) {
                    return i + 1;
                }
            }
            return -1;
        }
    }
}